/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {

  candidates = candidates.sort((a, b) => (a - b));
  let result = [], tempArr = [], used = new Array(candidates.length).fill(false);

  function dfs(remain, begin) {
    if(remain == 0) {
      result.push([...tempArr]);
      return;
    }

    for(let i = begin; i < candidates.length; i++) {
      if(remain - candidates[i] >= 0) {
        // i > begin的意思是，如果从这一次深搜开始，若每一次与上一次一样的话，就需要跳过了
        if(i > begin && !used[i - 1] && candidates[i] == candidates[i - 1]) {
          continue;
        }
        tempArr.push(candidates[i]);
        used[i] = true;
        dfs(remain - candidates[i], i + 1);
        used[i] = false;
        tempArr.splice(tempArr.length - 1, 1);
      }
    }
  }
  dfs(target, 0)

  return result;
};
let candidates = [10,1,2,7,6,1,5], target = 8;
console.log(combinationSum2(candidates, target));
candidates = [2,5,2,1,2], target = 5;
console.log(combinationSum2(candidates, target))
candidates = [3,1,3,5,1,1], target = 8;
console.log(combinationSum2(candidates, target));
candidates = [2, 2, 2], target = 2;
console.log(combinationSum2(candidates, target));
